`timescale 1ns / 1ps
//////////////////////////////////////////////////////////////////////////////////
// Company: 
// Engineer: tocanemis
// 
// Create Date: 2022/03/21 10:37:13
// Design Name: 
// Module Name: cuckoo_hash
// Project Name: 
// Target Devices: 
// Tool Versions: 
// Description: 
// 
// Dependencies: 
// 
// Revision:
// Revision 0.01 - File Created
// Additional Comments:
// 
//////////////////////////////////////////////////////////////////////////////////

//`define XILINX_IP

(* dont_touch="true" *)

module cuckoo_hash #(
    parameter               SN  =   1,      //slot number
                            HW  =   10,     //hash width
                            DW  =   32,     //data width
                            RN  =   1,      //reinsert number
                            RCW =   8       //reinsert counter width
    )(
    //system signals
    input                   clk,
    input                   rst_n,

    //insert
    input                   insert_i,
    input   [DW-1:0]        insert_data_i,
    output                  insert_error_o,
    output                  insert_end_o,

    //delete
    input                   delete_i,
    input   [DW-1:0]        delete_data_i,
    output                  delete_error_o,
    output                  delete_end_o,

    //search port-a
    input                   search_a_i,
    input   [DW-1:0]        search_a_data_i,
    output                  search_a_exist_o,
    output                  search_a_end_o,

    //search port-b
    input                   search_b_i,
    input   [DW-1:0]        search_b_data_i,
    output                  search_b_exist_o,
    output                  search_b_end_o,

    //RAM A interface
    //side A
    output                  rama_wea_o,
    output  [HW-1:0]        rama_addra_o,
    output  [(DW+1)*SN-1:0] rama_dina_o,
    input   [(DW+1)*SN-1:0] rama_douta_i,

    //side B
    output                  rama_web_o,
    output  [HW-1:0]        rama_addrb_o,
    output  [(DW+1)*SN-1:0] rama_dinb_o,
    input   [(DW+1)*SN-1:0] rama_doutb_i,

    //RAM B interface
    //side A
    output                  ramb_wea_o,
    output  [HW-1:0]        ramb_addra_o,
    output  [(DW+1)*SN-1:0] ramb_dina_o,
    input   [(DW+1)*SN-1:0] ramb_douta_i,

    //side B
    output                  ramb_web_o,
    output  [HW-1:0]        ramb_addrb_o,
    output  [(DW+1)*SN-1:0] ramb_dinb_o,
    input   [(DW+1)*SN-1:0] ramb_doutb_i
    );

    //------------Declare Signals----------------
    //register
    reg                     insert_r;
    reg                     insert_rr;

    reg                     delete_r;
    reg                     delete_rr;

    reg                     search_a_r;
    reg                     search_a_rr;

    reg                     search_b_r;
    reg                     search_b_rr;

    //insert
    wire                    insert;
    wire    [DW-1:0]        insert_data;
    wire    [RCW-1:0]       reinsert_cnt;
    reg     [RCW-1:0]       reinsert_cnt_r;
    reg     [RCW-1:0]       reinsert_cnt_rr;

    //hash calculate
    wire                    hash_a_valid;
    wire    [DW-1:0]        hash_a_data;
    reg     [DW-1:0]        hash_a_data_r;
    reg     [DW-1:0]        hash_a_data_rr;

    wire                    hasha_a_result_valid;
    wire    [HW-1:0]        hasha_a_result;
    reg     [HW-1:0]        hasha_a_result_r;
    wire                    hashb_a_result_valid;
    wire    [HW-1:0]        hashb_a_result;
    reg     [HW-1:0]        hashb_a_result_r;

    wire                    hash_b_valid;
    wire    [DW-1:0]        hash_b_data;
    reg     [DW-1:0]        hash_b_data_r;
    reg     [DW-1:0]        hash_b_data_rr;

    wire                    hasha_b_result_valid;
    wire    [HW-1:0]        hasha_b_result;
    wire                    hashb_b_result_valid;
    wire    [HW-1:0]        hashb_b_result;

    //search hash table
    wire    [HW-1:0]        rama_rd_addra;
    wire    [HW-1:0]        rama_rd_addrb;
    reg                     rama_rd_dataa_valid;
    reg                     rama_rd_datab_valid;

    wire    [HW-1:0]        ramb_rd_addra;
    wire    [HW-1:0]        ramb_rd_addrb;
    reg                     ramb_rd_dataa_valid;
    reg                     ramb_rd_datab_valid;

    wire    [SN-1:0]        rama_blank_slot;
    wire    [2*SN-1:0]      rama_double_blank_slot;
    wire    [2*SN-1:0]      rama_double_blank_slot_temp;
    wire    [SN-1:0]        rama_min_blank_slot;

    wire    [SN-1:0]        ramb_blank_slot;
    wire    [2*SN-1:0]      ramb_double_blank_slot;
    wire    [2*SN-1:0]      ramb_double_blank_slot_temp;
    wire    [SN-1:0]        ramb_min_blank_slot;

    wire    [SN-1:0]        rama_exist_a_slot;
    wire    [SN-1:0]        rama_exist_b_slot;
    wire                    rama_exist_a;
    wire                    rama_exist_b;

    wire    [SN-1:0]        ramb_exist_a_slot;
    wire    [SN-1:0]        ramb_exist_b_slot;
    wire                    ramb_exist_a;
    wire                    ramb_exist_b;

    //insert or delete
    reg                     random_ram;
    reg     [SN-1:0]        random_slot;
    reg                     select_ram;

    wire                    rama_insert_valid;
    wire                    ramb_insert_valid;
    wire                    rama_reinsert_valid;
    wire                    ramb_reinsert_valid;

    wire    [SN-1:0]        rama_insert_slot;
    wire    [SN-1:0]        ramb_insert_slot;

    wire                    rama_wr;
    wire    [HW-1:0]        rama_wr_addr;
    wire    [(DW+1)*SN-1:0] rama_wr_data_insert;
    wire    [(DW+1)*SN-1:0] rama_wr_data_delete;
    wire    [(DW+1)*SN-1:0] rama_wr_data;

    wire                    ramb_wr;
    wire    [HW-1:0]        ramb_wr_addr;
    wire    [(DW+1)*SN-1:0] ramb_wr_data_insert;
    wire    [(DW+1)*SN-1:0] ramb_wr_data_delete;
    wire    [(DW+1)*SN-1:0] ramb_wr_data;

    //kicked out data
    wire    [DW-1:0]        rama_kicked_data_mem    [SN-1:0];
    wire    [DW-1:0]        ramb_kicked_data_mem    [SN-1:0];
    wire    [SN-1:0]        kicked_data_mem         [DW-1:0];
    wire    [DW-1:0]        kicked_data;

    //reinsert
    wire                    reinsert_fifo_wr_en;
    wire    [DW+8-1:0]      reinsert_fifo_din;
    wire                    reinsert_fifo_full;

    wire                    reinsert_fifo_rd_en;
    wire    [DW+8-1:0]      reinsert_fifo_dout;
    wire                    reinsert_fifo_empty;

    //output
    reg                     insert_error;
    reg                     insert_end;

    reg                     delete_error;
    reg                     delete_end;

    //---------------Processing------------------
    //register
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            // reset
            insert_r        <=  1'b0;
            insert_rr       <=  1'b0;
            delete_r        <=  1'b0;
            delete_rr       <=  1'b0;
            search_a_r      <=  1'b0;
            search_a_rr     <=  1'b0;
            search_b_r      <=  1'b0;
            search_b_rr     <=  1'b0;
        end
        else begin
            insert_r        <=  insert;
            insert_rr       <=  insert_r;
            delete_r        <=  delete_i;
            delete_rr       <=  delete_r;
            search_a_r      <=  search_a_i;
            search_a_rr     <=  search_a_r;
            search_b_r      <=  search_b_i;
            search_b_rr     <=  search_b_r;
        end
    end

    //step 0: hash calculate
    //get insert data and reinsert cnt
    assign  insert          =   insert_i | reinsert_fifo_rd_en;
    assign  insert_data     =   insert_i?insert_data_i:reinsert_fifo_dout[DW-1:0];
    assign  reinsert_cnt    =   insert_i?{RCW{1'b0}}:reinsert_fifo_dout[DW+RCW-1:DW];

    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            // reset
            reinsert_cnt_r  <=  {RCW{1'b0}};
            reinsert_cnt_rr <=  {RCW{1'b0}};
        end
        else begin
            reinsert_cnt_r  <=  reinsert_cnt;
            reinsert_cnt_rr <=  reinsert_cnt_r;
        end
    end

    //for insert/delete/search_a
    assign  hash_a_valid    =   insert | delete_i | search_a_i;
    assign  hash_a_data     =   insert?insert_data:
                                delete_i?delete_data_i:
                                search_a_i?search_a_data_i:{DW{1'h0}};

    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            // reset
            hash_a_data_r   <=  {DW{1'b0}};
            hash_a_data_rr  <=  {DW{1'b0}};
        end
        else begin
            hash_a_data_r   <=  hash_a_data;
            hash_a_data_rr  <=  hash_a_data_r;
        end
    end

    CRC32_D32 #(
        .HW                 (HW),
        .HIGH               (0)
    ) U0_CRC32_D32(
        .clk                (clk),
        .rst_n              (rst_n),

        .calc_data_i        (hash_a_data),
        .calc_en_i          (hash_a_valid),

        .crc32_o            (hasha_a_result),
        .crc32_valid_o      (hasha_a_result_valid)
    );

    CRC32_D32 #(
        .HW                 (HW),
        .HIGH               (1)
    ) U1_CRC32_D32(
        .clk                (clk),
        .rst_n              (rst_n),

        .calc_data_i        (hash_a_data),
        .calc_en_i          (hash_a_valid),

        .crc32_o            (hashb_a_result),
        .crc32_valid_o      (hashb_a_result_valid)
    );

    always @ (posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            hasha_a_result_r    <=  {HW{1'b0}};
            hashb_a_result_r    <=  {HW{1'b0}};
        end
        else begin
            hasha_a_result_r    <=  hasha_a_result;
            hashb_a_result_r    <=  hashb_a_result;
        end
    end

    //for insert/delete/search_a
    assign  hash_b_valid    =   search_b_i;
    assign  hash_b_data     =   search_b_i?search_b_data_i:{DW{1'h0}};

    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            // reset
            hash_b_data_r   <=  {DW{1'b0}};
            hash_b_data_rr  <=  {DW{1'b0}};
        end
        else begin
            hash_b_data_r   <=  hash_b_data;
            hash_b_data_rr  <=  hash_b_data_r;
        end
    end

    CRC32_D32 #(
        .HW                 (HW),
        .HIGH               (0)
    ) U2_CRC32_D32(
        .clk                (clk),
        .rst_n              (rst_n),

        .calc_data_i        (hash_b_data),
        .calc_en_i          (hash_b_valid),

        .crc32_o            (hasha_b_result),
        .crc32_valid_o      (hasha_b_result_valid)
    );

    CRC32_D32 #(
        .HW                 (HW),
        .HIGH               (1)
    ) U3_CRC32_D32(
        .clk                (clk),
        .rst_n              (rst_n),

        .calc_data_i        (hash_b_data),
        .calc_en_i          (hash_b_valid),

        .crc32_o            (hashb_b_result),
        .crc32_valid_o      (hashb_b_result_valid)
    );

    //step 1: search hash table
    assign  rama_rd_addra       =   hasha_a_result;
    assign  rama_rd_addrb       =   hasha_b_result;

    assign  ramb_rd_addra       =   hashb_a_result;
    assign  ramb_rd_addrb       =   hashb_b_result;

    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            // reset
            rama_rd_dataa_valid <=  1'b0;
            rama_rd_datab_valid <=  1'b0;

            ramb_rd_dataa_valid <=  1'b0;
            ramb_rd_datab_valid <=  1'b0;
        end
        else begin
            rama_rd_dataa_valid <=  hasha_a_result_valid;
            rama_rd_datab_valid <=  hasha_b_result_valid;

            ramb_rd_dataa_valid <=  hashb_a_result_valid;
            ramb_rd_datab_valid <=  hashb_b_result_valid;
        end
    end

    //insert: confirm blank slot
    generate
        genvar i;
        for (i=0;i<SN;i=i+1) begin:confirm_blank_slot
            assign  rama_blank_slot[i]  =   rama_rd_dataa_valid & (~rama_douta_i[(DW+1)*(i+1)-1]);
            assign  ramb_blank_slot[i]  =   ramb_rd_dataa_valid & (~ramb_douta_i[(DW+1)*(i+1)-1]);
        end
    endgenerate

    assign  rama_double_blank_slot      =   {rama_blank_slot,rama_blank_slot};
    assign  rama_double_blank_slot_temp =   rama_double_blank_slot & (~(rama_double_blank_slot - {{(2*SN-1){1'b0}},{1'b1}}));
    assign  rama_min_blank_slot         =   (rama_double_blank_slot_temp[2*SN-1:SN] | rama_double_blank_slot_temp[SN-1:0]) & (~{SN{rama_exist_a}});

    assign  ramb_double_blank_slot      =   {ramb_blank_slot,ramb_blank_slot};
    assign  ramb_double_blank_slot_temp =   ramb_double_blank_slot & (~(ramb_double_blank_slot - {{(2*SN-1){1'b0}},{1'b1}}));
    assign  ramb_min_blank_slot         =   (ramb_double_blank_slot_temp[2*SN-1:SN] | ramb_double_blank_slot_temp[SN-1:0]) & (~{SN{ramb_exist_a}});

    //delete: confirm exist slot
    generate
        genvar j;
        for (j=0;j<SN;j=j+1) begin:confirm_exist_slot
            assign  rama_exist_a_slot[j]    =   rama_rd_dataa_valid & (rama_douta_i[(DW+1)*(j+1)-1]) & (hash_a_data_rr == rama_douta_i[(DW+1)*(j+1)-2:(DW+1)*j]);
            assign  rama_exist_b_slot[j]    =   rama_rd_datab_valid & (rama_doutb_i[(DW+1)*(j+1)-1]) & (hash_b_data_rr == rama_doutb_i[(DW+1)*(j+1)-2:(DW+1)*j]);

            assign  ramb_exist_a_slot[j]    =   ramb_rd_dataa_valid & (ramb_douta_i[(DW+1)*(j+1)-1]) & (hash_a_data_rr == ramb_douta_i[(DW+1)*(j+1)-2:(DW+1)*j]);
            assign  ramb_exist_b_slot[j]    =   ramb_rd_datab_valid & (ramb_doutb_i[(DW+1)*(j+1)-1]) & (hash_b_data_rr == ramb_doutb_i[(DW+1)*(j+1)-2:(DW+1)*j]);
        end
    endgenerate

    //search: confirm exist
    assign  rama_exist_a        =   |rama_exist_a_slot;
    assign  rama_exist_b        =   |rama_exist_b_slot;

    assign  ramb_exist_a        =   |ramb_exist_a_slot;
    assign  ramb_exist_b        =   |ramb_exist_b_slot;

    //step 2: insert or delete
    always @ (posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            random_ram          <=  1'b0;
        end
        else begin
            random_ram          <=  ~random_ram;
        end
    end

    generate
        if (SN == 1) begin
            always @ (posedge clk or negedge rst_n) begin
                if (!rst_n) begin
                    random_slot         <=  1'b1;
                end
                else begin
                    random_slot         <=  1'b1;
                end
            end
        end
        else if (SN == 2) begin
            always @ (posedge clk or negedge rst_n) begin
                if (!rst_n) begin
                    random_slot         <=  2'b01;
                end
                else begin
                    random_slot         <=  {random_slot[0],random_slot[1]};
                end
            end
        end
        else begin
            always @ (posedge clk or negedge rst_n) begin
                if (!rst_n) begin
                    random_slot         <=  {{(SN-1){1'b0}},1'b1};
                end
                else begin
                    random_slot         <=  {random_slot[SN-2:0],random_slot[SN-1]};
                end
            end
        end
    endgenerate

    always @ (*) begin
        case({{|rama_min_blank_slot},{|ramb_min_blank_slot}})
            2'b00:select_ram    <=  random_ram;
            2'b01:select_ram    <=  1'b0;
            2'b10:select_ram    <=  1'b1;
            2'b11:select_ram    <=  rama_min_blank_slot < ramb_min_blank_slot;  //0:ramb;1:rama
            default:select_ram  <=  1'b0;
        endcase
    end

    //insert valid
    assign  rama_insert_valid   =   insert_rr & (|rama_min_blank_slot) & select_ram;
    assign  ramb_insert_valid   =   insert_rr & (|ramb_min_blank_slot) & (~select_ram);

    //reinsert valid
    assign  rama_reinsert_valid =   insert_rr & (~(|rama_min_blank_slot)) & (~(|ramb_min_blank_slot)) & select_ram;
    assign  ramb_reinsert_valid =   insert_rr & (~(|rama_min_blank_slot)) & (~(|ramb_min_blank_slot)) & (~select_ram);

    assign  rama_wr             =   (rama_insert_valid | rama_reinsert_valid) | (delete_rr & rama_exist_a);
    assign  rama_wr_addr        =   hasha_a_result_r;

    assign  ramb_wr             =   (ramb_insert_valid | ramb_reinsert_valid) | (delete_rr & ramb_exist_a);
    assign  ramb_wr_addr        =   hashb_a_result_r;

    generate
        genvar k;
        for (k=0;k<SN;k=k+1) begin:gen_ram_wr_data
            assign  rama_insert_slot[k]                             =   (rama_insert_valid & rama_min_blank_slot[k]) | (rama_reinsert_valid & random_slot[k]);
            assign  ramb_insert_slot[k]                             =   (ramb_insert_valid & ramb_min_blank_slot[k]) | (ramb_reinsert_valid & random_slot[k]);

            assign  rama_wr_data_insert[(DW+1)*(k+1)-1:(DW+1)*k]    =   rama_insert_slot[k]?{1'b1,hash_a_data_rr}:rama_douta_i[(DW+1)*(k+1)-1:(DW+1)*k];
            assign  ramb_wr_data_insert[(DW+1)*(k+1)-1:(DW+1)*k]    =   ramb_insert_slot[k]?{1'b1,hash_a_data_rr}:ramb_douta_i[(DW+1)*(k+1)-1:(DW+1)*k];
            
            assign  rama_wr_data_delete[(DW+1)*(k+1)-1:(DW+1)*k]    =   delete_rr && rama_exist_a_slot[k]?{1'b0,{DW{1'b0}}}:rama_douta_i[(DW+1)*(k+1)-1:(DW+1)*k];
            assign  ramb_wr_data_delete[(DW+1)*(k+1)-1:(DW+1)*k]    =   delete_rr && ramb_exist_a_slot[k]?{1'b0,{DW{1'b0}}}:ramb_douta_i[(DW+1)*(k+1)-1:(DW+1)*k];
        end
    endgenerate

    assign  rama_wr_data            =   (delete_rr & rama_exist_a)?rama_wr_data_delete:rama_wr_data_insert;
    assign  ramb_wr_data            =   (delete_rr & ramb_exist_a)?ramb_wr_data_delete:ramb_wr_data_insert;

    //step 3: write the kicked out data to FIFO
    //the kicked out data
    generate
        genvar n,m;
        for (n=0;n<SN;n=n+1) begin:gen_ram_kicked_data_mem
            assign  rama_kicked_data_mem[n]     =   {DW{rama_reinsert_valid & random_slot[n]}} & rama_douta_i[(DW+1)*(n+1)-1:(DW+1)*n];
            assign  ramb_kicked_data_mem[n]     =   {DW{ramb_reinsert_valid & random_slot[n]}} & ramb_douta_i[(DW+1)*(n+1)-1:(DW+1)*n];

            for (m=0;m<DW;m=m+1) begin:gen_kicked_data_mem
                assign  kicked_data_mem[m][n]   =   rama_kicked_data_mem[n][m] | ramb_kicked_data_mem[n][m];
            end
        end
    endgenerate

    generate
        genvar l;
        for (l=0;l<DW;l=l+1) begin:gen_kicked_data
            assign  kicked_data[l]              =   |kicked_data_mem[l];
        end
    endgenerate

    //write/read fifo
    assign  reinsert_fifo_wr_en     =   (rama_reinsert_valid | ramb_reinsert_valid) & (reinsert_cnt_rr <= RN) & (~reinsert_fifo_full);
    assign  reinsert_fifo_din       =   {reinsert_cnt_rr+{{(RCW-1){1'b0}},1'b1},kicked_data};

    assign  reinsert_fifo_rd_en     =   (~insert_i) & (~reinsert_fifo_empty);

`ifdef XILINX_IP

    reinsert_fifo U_reinsert_fifo (
        //system signals
        .clk                (clk),      // input wire clk
        .rst                (~rst_n),      // input wire rst

        //write side
        .wr_en              (reinsert_fifo_wr_en),  // input wire wr_en
        .din                (reinsert_fifo_din),      // input wire [35 : 0] din
        .full               (reinsert_fifo_full),    // output wire full

        .rd_en              (reinsert_fifo_rd_en),  // input wire rd_en
        .dout               (reinsert_fifo_dout),    // output wire [35 : 0] dout
        .empty              (reinsert_fifo_empty)  // output wire empty
    );

`else

    syn_fifo_fwft #(
        .FDW                (DW+RCW),       //fifo data width
        .FDPW               (HW),           //fifo depth width the depth of the fifo is 2^FDPW
        .HT                 (3),            //larger than this value 1'b1,prog_full threshhold
        .LT                 (2)             //less than this value 1'b1, prog_empty threshhold
    ) U_reinsert_fifo(
        //system signal
        .clk                (clk),
        .rst_n              (rst_n),

        //write side
        .wr_en              (reinsert_fifo_wr_en),
        .din                (reinsert_fifo_din),
        .full               (reinsert_fifo_full),

        //read side
        .rd_en              (reinsert_fifo_rd_en),
        .dout               (reinsert_fifo_dout),
        .empty              (reinsert_fifo_empty)
    );

`endif

    //------------Output Signals-----------------
    //insert
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            // reset
            insert_error        <=  1'b0;
            insert_end          <=  1'b0;
        end
        else begin
            insert_error        <=  insert_rr & (~rama_insert_valid) & (~ramb_insert_valid) & (~reinsert_fifo_wr_en);
            insert_end          <=  insert_rr;
        end
    end

    assign  insert_error_o      =   insert_error;
    assign  insert_end_o        =   insert_end;

    //delete
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            // reset
            delete_error        <=  1'b0;
            delete_end          <=  1'b0;
        end
        else begin
            delete_error        <=  delete_rr & (~rama_exist_a) & (~ramb_exist_a);
            delete_end          <=  delete_rr;
        end
    end

    assign  delete_error_o      =   delete_error;
    assign  delete_end_o        =   delete_end;

    //search
    assign  search_a_exist_o    =   search_a_rr & (rama_exist_a | ramb_exist_a);
    assign  search_a_end_o      =   search_a_rr;

    assign  search_b_exist_o    =   search_b_rr & (rama_exist_b | ramb_exist_b);
    assign  search_b_end_o      =   search_b_rr;

    //RAM A
    assign  rama_wea_o          =   1'b0;
    assign  rama_addra_o        =   rama_rd_addra;
    assign  rama_dina_o         =   {((DW+1)*SN){1'b0}};

    assign  rama_web_o          =   rama_wr;
    assign  rama_addrb_o        =   rama_wr?rama_wr_addr:rama_rd_addrb;
    assign  rama_dinb_o         =   rama_wr?rama_wr_data:{((DW+1)*SN){1'b0}};

    //RAM B
    assign  ramb_wea_o          =   1'b0;
    assign  ramb_addra_o        =   ramb_rd_addra;
    assign  ramb_dina_o         =   {((DW+1)*SN){1'b0}};

    assign  ramb_web_o          =   ramb_wr;
    assign  ramb_addrb_o        =   ramb_wr?ramb_wr_addr:ramb_rd_addrb;
    assign  ramb_dinb_o         =   ramb_wr?ramb_wr_data:{((DW+1)*SN){1'b0}};

    //------------Debug Signals------------------
endmodule
